package sword.chapter9Heap;

import java.util.*;

/**
 * 出现频率最高的k个数字
 *
 * 方法1
 * 1. HashMap统计数字出现次数
 * 2. 创建PriorityQueue时指定为升序排列（最小堆），值存储 Map.Entry对象，计算第k大的元素
 * 3. 读取最小堆元素
 *
 * 方法2
 * HashMap统计数字出现次数，根据value排序也可以解此题（借助Collections.sort()排序方法）
 * 升序：o1 - o2 或 o1.compareTO(o2)
 * 降序：o2 - o1 或 o2.compareTO(o1)
 * @author K
 * @date 2021/12/14 09:08
 */
public class S60TopKFrequent {

    public static List<Integer> s60(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(hashMap.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                //降序
                return o2.getValue() - o1.getValue();
            }
        });

        ArrayList<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : list) {
            if (result.size() < k) {
                result.add(entry.getKey());
            } else {
                break;
            }
        }

        return result;
    }

    public static List<Integer> s60A(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        //创建最小堆
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                // 升序排列
                return o1.getValue() - o2.getValue();
            }
        });

        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else if (minHeap.peek().getValue() < entry.getValue()) {
                minHeap.poll();
                minHeap.offer(entry);
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(minHeap.poll().getKey());
        }
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 1, 3, 3, 1};
        List<Integer> result = s60(nums, 2);
        List<Integer> result2 = s60A(nums, 2);
        System.out.println();
    }
}
